/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM72 连续子数组的最大和
 * <a href="https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=295&tqId=23259&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-10
 * Time: 22:22
 */

//在动态规划的思想上进行优化，做到空间复杂度位O（1）
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //题目中保证数组不为空
        int max = array[0];  //记录连续子数组的最大和
        int sum = array[0];
        //跟据推理公式遍历整个数组
        //sum记录的是以array[i-1]作为结尾的最大的字串的和
        for (int i = 1; i < array.length; i++) {
            sum = Math.max(sum + array[i],array[i]);
            max = Math.max(sum,max);
        }
        return max;
    }
}

